class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> len(n, 1), count(n, 1);

        // 两个小贪心思想：一次遍历找出最大值及其出现次数
        int maxval = len[0], ret = count[0];
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[j] < nums[i])
                {
                    if(len[j] + 1 == len[i])
                        count[i] += count[j];
                    else if(len[j] + 1 > len[i])
                        len[i] = len[j] + 1, count[i] = count[j];
                }
            }
            if(len[i] > maxval)
                ret = count[i], maxval = len[i];
            else if(len[i] == maxval)
                ret += count[i];
        }

        // for(int x : len)
        //     cout << x << " ";
        // cout << "\n";
        // for(int x : count)
        //     cout << x << " ";
        // cout << "\n";

        // int maxval = len[0], ret = count[0];
        // for(int i = 1; i < n; i++)
        // {
        //     if(len[i] > maxval)
        //         ret = count[i], maxval = len[i];
        //     else if(len[i] == maxval)
        //         ret += count[i];
        // }

        return ret;
    }
};